import java.util.*;

public class Main {
    // 方向映射
    private static final Map<Character, int[]> DIRECTIONS = new HashMap<>();

    static {
        DIRECTIONS.put('U', new int[]{-1, 0});
        DIRECTIONS.put('D', new int[]{1, 0});
        DIRECTIONS.put('L', new int[]{0, -1});
        DIRECTIONS.put('R', new int[]{0, 1});
    }

    private static final Set<Character> TRANSPORTERS = DIRECTIONS.keySet();

    public static int solution(int N, int M, char[][] data) {
        boolean[][] visited = new boolean[N][M];
        Queue<int[]> queue = new LinkedList<>();

        // 初始化：找到所有出口 'O'
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (data[i][j] == 'O') {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        int reachableCount = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            reachableCount++;

            // 检查四个方向
            for (int[] dir : DIRECTIONS.values()) {
                int nx = x + dir[0];
                int ny = y + dir[1];

                // 边界检查
                if (nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny]) {
                    char cell = data[nx][ny];

                    // 如果是传送器
                    if (TRANSPORTERS.contains(cell)) {
                        int[] tDir = DIRECTIONS.get(cell);
                        // 判断是否能从该传送器传送到当前位置
                        if (nx + tDir[0] == x && ny + tDir[1] == y) {
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                        }
                    } else {
                        // 普通格子
                        visited[nx][ny] = true;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        return N * M - reachableCount;
    }

    public static void main(String[] args) {
        // Test Case 1
        char[][] data1 = {
            {'.', '.', '.', '.', '.'},
            {'.', 'R', 'R', 'D', '.'},
            {'.', 'U', '.', 'D', 'R'},
            {'.', 'U', 'L', 'L', '.'},
            {'.', '.', '.', '.', 'O'}
        };
        System.out.println(solution(5, 5, data1) == 10); // true

        // Test Case 2
        char[][] data2 = {
            {'.', 'R', '.', 'O'},
            {'U', '.', 'L', '.'},
            {'.', 'D', '.', '.'},
            {'.', '.', 'R', 'D'}
        };
        System.out.println(solution(4, 4, data2) == 2); // true

        // Test Case 3
        char[][] data3 = {
            {'.', 'U', 'O'},
            {'L', '.', 'R'},
            {'D', '.', '.'}
        };
        System.out.println(solution(3, 3, data3) == 8); // true
    }
}